#include <stdio.h>

void Swap(int* a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void print(int *a, int n)
{
    for(int i = 0; i < n; ++i)
        printf("%d ", a[i]);
    printf("\n");
}
void insert(int* a, int n)
{
   for (int i = 0; i < n - 1; ++i)
   {
        for(int j = i; j >= 0; --j)
        {
            if(a[j] > a[j + 1])
                Swap(&a[j], &a[j + 1]);
            else 
                break;
        }
   }
}
void shell(int*a, int n)
{
    for(int gap = n / 2; gap >= 1; gap /= 2)
    {
        for(int i = 0; i < n - gap; ++i)
        {
            for(int j = i; j >= 0; j -= gap)
            {
                if(a[j] > a[j + gap])
                    Swap(&a[j], &a[j + gap]);
                else 
                    break;
            }
        }
    }
}
void AdjustDown(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while(child < size)
    {
        if (child + 1 < size && a[child] > a[child + 1])
            ++child;
        if (a[parent] > a[child])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else 
        {
            break;
        }
    }
}
void Heapsort(int* a, int n)
{
    for (int i = (n - 1 - 1); i >= 0; --i)
    {
        AdjustDown(a, n - 1, i);
    }
    for (int i = n; i > 0; --i)
    {
        Swap(&a[0], &a[i - 1]);
        AdjustDown(a, i - 1, 0);
    }
}

void select(int* a, int n)
{
    int left = 0, right = n -1;
    while (left < right)
    {
        int mini  = left;
        int maxi = right;
        for (int begin = left; begin <= right; ++begin)
        {
            if (a[begin] <= a[mini])
                mini = begin;
            if (a[begin] > a[maxi])
                maxi = begin;
        }
        Swap(&a[left], &a[mini]);
        if(maxi == left)
        {
            maxi = mini;
        }
        Swap(&a[right], &a[maxi]);
        ++left;
        --right;
    }
}

int GetMiniInsid(int* a, int begin, int end)
{
    int mini = begin + ((end - begin) >> 1);
    if(a[begin] > a[mini])
    {
        if(a[mini] > a[end])
            return mini;
        else  if (a[begin] > a[end])
            return end;
        else 
            return begin;
    }
    else
    {
        if(a[end] > a[mini])
            return mini;
        else if (a[begin] > a[end])
            return begin;
        else 
            return end;
    }
}

int partion1(int* a, int begin, int end)
{
    int mini = GetMiniInsid(a, begin, end);
    Swap(&a[begin], &a[mini]);

    int keyi = begin;
    while(begin < end)
    {
        while (begin < end && a[end] > a[keyi]) 
            --end;
        while (begin < end && a[begin] <= a[keyi])
            ++begin;
        Swap(&a[begin], &a[end]);
    }
    Swap(&a[begin], &a[keyi]);
    return begin;
}

int partion2(int* a, int begin, int end)
{
    int mini = GetMiniInsid(a, begin, end);
    Swap(&a[begin], &a[mini]);

    int pit = a[begin];
    while(begin < end)
    {
        while (begin < end && a[end] > pit)
            --end;
        Swap(&a[begin], &a[end]);
        while (begin < end && a[begin] <= pit)
            ++begin;
        Swap(&a[begin], &a[end]);
    }

    return begin;
}
int partion3(int* a, int begin, int end)
{
    int mini = GetMiniInsid(a, begin, end);
    Swap(&a[begin], &a[mini]);

    int keyi = begin;
    int prev = keyi;
    int cur = prev + 1;
    while(cur <= end)
    {
        if(a[cur] < a[keyi] && prev != cur)
            Swap(&a[++prev], &a[cur]); 
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    return prev;
}
void quicksort(int* a, int left, int right)
{
    if (left > right)
        return ;
    //int keyi = partion1(a, left, right);
    //int keyi = partion2(a, left, right);
    int keyi = partion3(a, left, right);
    print(a, 10);
    quicksort(a, left, keyi - 1);
    quicksort(a, keyi + 1, right);
}


void QuickSortNoRe(int* a, int left, int right)
{
    
}

void test1()
{
    int a[10] = {12, 10, 6, 8, 18, 5, 40, 3, 1, 9};
    print(a, 10);
    insert(a, 10);
    printf("insert :: ");
    print(a, 10);
}

void test2()
{
    int a[10] = {12, 10, 6, 8, 18, 5, 40, 3, 1, 9};
    print(a, 10);
    shell(a, 10);
    printf("shell :: ");
    print(a, 10);
}


void test3()
{
    int a[10] = {12, 10, 6, 8, 18, 5, 40, 3, 1, 9};
    print(a, 10);
    Heapsort(a, 10);
    printf("Heapsort :: ");
    print(a, 10);
}
void test4()
{
    int a[10] = {12, 10, 6, 8, 18, 5, 40, 3, 1, 9};
    print(a, 10);
    select(a, 10);
    printf("select :: ");
    print(a, 10);
}
void test5()
{
    int a[10] = {12, 10, 6, 8, 18, 5, 40, 3, 1, 9};
    print(a, 10);
    quicksort(a, 0, 9 );
    printf("quicksort :: ");
    print(a, 10);
}

int main()
{
    //bintest1();
    //test2();
    //test3();
    //test4();
    test5();
    return 0;
}
